#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int maxSum(vector<int> array) {
  vector<vector<int>> numbers;
  if (array.size() == 0) {
    return 0;
  } else if (array.size() == 1) {
    numbers.push_back({array[0]});
    return array[0];
  } 

  vector<int> ans = array;
  numbers.push_back({array[0]});
  ans[1] = max(ans[0], array[1]); 
  numbers.push_back({ans[1]});

  for (int i = 2; i < array.size(); ++i) {
    if (ans[i - 1] > ans[i - 2] + array[i]) {
      numbers.push_back(numbers[i - 1]);
      ans[i] = ans[i - 1];
    } else {
      ans[i] = ans[i - 2] + array[i];
      vector<int> tmp = numbers[i - 2];
      tmp.push_back(array[i]);
      numbers.push_back(tmp);
    }
    
  }
  for (int i : *numbers.rbegin()) {
    cout << i << " + ";
  }
  cout << endl;
  
  return *ans.rbegin();
}

int main(int argc, char const *argv[]) {
  cout << maxSum({75, 105, 120, 75, 90, 135}) << endl;
  return 0;
}
